package pers.qianyu.month_202102.date_20210226;

import java.util.*;

/**
 * 1178. 猜字谜
 * https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/
 *
 * @author mizzle rain
 * @date 2021-02-26 11:15
 */
public class FindNumOfValidWords {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        HashMap<Integer, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            int bit = getBit(word);
            wordMap.put(bit, wordMap.getOrDefault(bit, 0) + 1);
        }

        ArrayList<Integer> answer = new ArrayList<>();
        for (String puzzle : puzzles) {
            int bit = getBit(puzzle);

            int first = puzzle.charAt(0) - 'a';
            int t = bit, cnt = 0;
            while (t > 0) {
                if (((1 << first) & t) != 0 && wordMap.getOrDefault(t, 0) > 0) {
                    cnt += wordMap.get(t);
                }
                t = (t - 1) & bit;
            }
            answer.add(cnt);
        }
        return answer;
    }

    private int getBit(String str) {
        char[] arr = str.toCharArray();
        int res = 0;
        for (char c : arr) {
            int t = c - 'a';
            res = res | (1 << t);
        }
        return res;
    }
}
